package 代码随想2._11单调栈;

/**
 * @author XXX
 * @date 2024-01-18 13:23
 */

import java.util.Arrays;
import java.util.Stack;

/**
 * https://leetcode.cn/problems/next-greater-element-ii/description/
 */
public class _3下一个更大元素II {
    public int[] nextGreaterElements(int[] nums) {
        if (nums == null || nums.length <= 1){
            return new int[]{-1};
        }
        int size = nums.length;
        int[] result = new int[size];//存放结果
        Arrays.fill(result, -1);
        Stack<Integer> st= new Stack<>();//栈中存放的是nums中的元素下标
        for (int i=0; i< 2*size; i++){
            while (!st.isEmpty() && nums[i % size] > nums[st.peek()]){
                result[st.peek()] = nums[i % size];
                st.pop();
            }
            st.push(i % size);
        }
        return result;
    }
}
